﻿/* * Write a program that sorts an array of integers using the merge sort algorithm (find it in Wikipedia). * */



using System;

class MergeSort
{
    static void Main()
    {
        uint N;
        bool iProvided = false;

        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer (>0).");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false || N < 1);

        iProvided = false; //reset iProvided
        int[] nums = new int[N];
        for (int i = 0; i < nums.Length; i++)
        {
            iProvided = false;
            do
            {

                if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
                else iProvided = true;
                Console.Write("Enter element {0}: ", i + 1);
            } while (Int32.TryParse(Console.ReadLine(), out nums[i]) == false);
        }

        int[] numsCopy = (int[])nums.Clone();
        int[] numsCopy2 = new int[N];
        BottomUpSort(numsCopy.Length, numsCopy, numsCopy2);
        
        for (int i = 0; i < numsCopy2.Length; i++) Console.WriteLine(numsCopy2[i]);

        Console.WriteLine();

    }

    private static void BottomUpSort(int n, int[] A, int[] B)
    {
        int width;

        /* Each 1-element run in A is already "sorted". */

        /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted. */
        for (width = 1; width < n; width = 2 * width)
        {
            int i;

            /* Array A is full of runs of length width. */
            for (i = 0; i < n; i = i + 2 * width)
            {
                /* Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
                /* or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
                BottomUpMerge(A, i, Math.Min(i + width, n), Math.Min(i + 2 * width, n), B);
            }

            /* Now work array B is full of runs of length 2*width. */
            /* Copy array B to array A for next iteration. */
            /* A more efficient implementation would swap the roles of A and B */
            //CopyArray(A, B, n);
            A = (int[])B.Clone();
            /* Now array A is full of runs of length 2*width. */
        }
    }

    private static void BottomUpMerge(int[] A, int iLeft, int iRight, int iEnd, int[] B)
    {
      int i0 = iLeft;
      int i1 = iRight;
      int j;
 
      /* While there are elements in the left or right lists */
      for (j = iLeft; j < iEnd; j++)
        {
          /* If left list head exists and is <= existing right list head */
          if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
            {
              B[j] = A[i0];
              i0 = i0 + 1;
            }
          else
            {
              B[j] = A[i1];
              i1 = i1 + 1;
            }
        }
    }
}
